package org.example.Soution003;

import java.util.ArrayList;
import java.util.List;

public class DynamicProgrammingSonSequence {
    public static void main(String[] args) {
        int[] nums=new int[]{10,9,2,5,3,7,101,18};
        DynamicProgrammingSonSequence dp=new DynamicProgrammingSonSequence();
        System.out.println(dp.lengthOfLIS2(nums));
    }

    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];
        int allMax=0;
        for(int i=0;i<n;i++){
            int max=0;
            for(int j=0;j<i;j++){
                if(res[j]>max&&nums[j]<nums[i]){
                    max=res[j];
                }
            }
            res[i]=max+1;
            allMax=Math.max(allMax,res[i]);
        }
        return allMax;
    }

    public int lengthOfLIS2(int[] nums) {
        int n=nums.length;
        List<Integer> talis=new ArrayList<>();
        for(int i=0;i<n;i++){
            int tn=talis.size();
            if(talis.size()<=0){
                talis.add(nums[i]);
                continue;
            }
            if(talis.get(tn-1)<nums[i]){
                talis.add(nums[i]);
            }else{
                int temp=getNewPosition(talis,nums[i]);
                talis.set(temp,nums[i]);
            }
        }
        return talis.size();
    }

    public int getNewPosition(List<Integer> talis,int num){
        int start=0,end=talis.size()-1;
        while(start<=end){
            int mid=start+(end-start)/2;
            if(talis.get(mid)==num){
                return mid;
            }else if(talis.get(mid)>num){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return start;
    }
}
